package algorithm;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author Panbo Guo
 * @date 2021/7/14
 */
public class T00094 {

    public static void main(String[] args) {
        Integer[] arr = new Integer[]{1,null,2,3};
        TreeNode treeNode = TreeUtils.buildTree(arr);
        System.out.println(new Solution().inorderTraversal(treeNode));
    }

    static class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> list = new ArrayList<>();
            if (root != null) {
                Stack<TreeNode> stack = new Stack<>();
                TreeNode cur = root;
                for (; ;) {
                    if (cur == null) {
                        if (stack.isEmpty())
                            break;
                        cur = stack.pop();
                        list.add(cur.val);
                        cur = cur.right;
                    } else {
                        stack.push(cur);
                        cur = cur.left;
                    }
                }
            }
            return list;
        }
    }
}
